00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #ifndef __GRAPH_H__
00040 #define __GRAPH_H__
00041
00042 #include <string.h>
00043 #include "block.h"
00044
00045 #include <assert.h>
00046
00047 #include "dynamic/grow_vector.h"
00049
00050
00051
00055
00057 template <typename captype, typename tcaptype, typename flowtype> class Graph
00058 {
00059 public:
00060 typedef enum
00061 {
00062 SOURCE = 0,
00063 SINK = 1
00064 } termtype;
00065 typedef int node_id;
00066
00071
00085 Graph(int node_num_max, int edge_num_max, void (*err_function)(char *) = NULL);
00086
00088 ~Graph();
00089
00093 node_id add_node(int num = 1);
00094
00097 void add_edge(node_id i, node_id j, captype cap, captype rev_cap);
00098
00104 void add_tweights(node_id i, tcaptype cap_source, tcaptype cap_sink);
00105
00106
00110 flowtype maxflow(bool reuse_trees = false, Block<node_id>* changed_list = NULL);
00111
00117 termtype what_segment(node_id i, termtype default_segm = SOURCE);
00118
00119
00120
00122
00123
00125
00126 private:
00127 struct node;
00128 struct arc;
00129
00130 public:
00131
00133
00135
00145 void reset();
00146
00152
00158 typedef arc* arc_id;
00159 arc_id get_first_arc();
00160 arc_id get_next_arc(arc_id a);
00161
00163 int get_node_num() { return node_num; }
00164 int get_arc_num() { return (int)(arc_last - arcs); }
00165 void get_arc_ends(arc_id a, node_id& i, node_id& j);
00166
00170
00172 tcaptype get_trcap(node_id i);
00174 captype get_rcap(arc* a);
00175
00181 void set_trcap(node_id i, tcaptype trcap);
00182 void set_rcap(arc* a, captype rcap);
00183
00187
00208 void mark_node(node_id i);
00209
00245 void remove_from_changed_list(node_id i)
00246 {
00247 assert(i>=0 && i<node_num && nodes[i].is_in_changed_list);
00248 nodes[i].is_in_changed_list = 0;
00249 }
00250
00251
00252
00253
00254
00255
00259
00260 private:
00262
00263 struct node
00264 {
00265
00266 arc *first;
00267
00268
00269
00270 tcaptype tr_cap;
00271
00272 arc *parent;
00273 node *next;
00274 int DIST;
00275
00276
00277 int TS;
00278 int is_sink : 1;
00279 int is_in_changed_list : 1;
00280
00281 int is_marked : 1;
00282 int is_saved : 1;
00283 };
00284
00285 struct arc
00286 {
00287 node *head;
00288 arc *next;
00289 arc *sister;
00290
00291
00292 captype r_cap;
00293 int is_saved : 1;
00294 };
00295
00296 struct nodeptr
00297 {
00298 node *ptr;
00299 nodeptr *next;
00300 };
00301 static const int NODEPTR_BLOCK_SIZE = 128;
00302
00303 node *nodes, *node_last, *node_max;
00304 arc *arcs, *arc_last, *arc_max;
00305
00306 int node_num;
00307
00308 DBlock<nodeptr> *nodeptr_block;
00309
00310 void (*error_function)(char *);
00311
00312
00313
00314 flowtype flow;
00315
00317 int maxflow_iteration;
00318 Block<node_id> *changed_list;
00319
00321
00322 node *queue_first[2], *queue_last[2];
00323 nodeptr *orphan_first, *orphan_last;
00324 int TIME;
00325
00327
00328 void reallocate_nodes(int num);
00329 void reallocate_arcs();
00330
00332 void set_active(node *i);
00333 node *next_active();
00334
00336 void set_orphan_front(node* i);
00337 void set_orphan_rear(node* i);
00338
00339 void add_to_changed_list(node* i);
00340
00341 void maxflow_init();
00342 void maxflow_reuse_trees_init();
00343 void augment(arc *middle_arc);
00344 void process_source_orphan(node *i);
00345 void process_sink_orphan(node *i);
00346
00347 void test_consistency(node* current_node=NULL);
00348 private:
00349 class graph_save{
00350 public:
00351 bool started;
00352 struct node_saved{
00353 node saved;
00354 node * dest;
00355 node_saved (node *x):dest(x),saved(*x){};
00356 };
00357 struct arc_saved{
00358 arc saved;
00359 arc * dest;
00360 arc_saved (arc *x):dest(x),saved(*x){};
00361 };
00362
00363 dynamic::grow_vector<node_saved> nodes;
00364 dynamic::grow_vector<arc_saved> arcs;
00365 flowtype flow;
00366 int maxflow_iteration;
00367 node *queue_first[2], *queue_last[2];
00368 nodeptr *orphan_first, *orphan_last;
00369 int TIME;
00370
00371 };
00372
00373 public:
00374 graph_save save;
00375 void start_save(){
00376 for(int i=0;i<save.nodes.size();++i){
00377 save.nodes[i].dest->is_saved = false;
00378 };
00379 for(int i=0;i<save.arcs.size();++i){
00380 save.arcs[i].dest->is_saved = false;
00381 };
00382 save.nodes.clear();
00383 save.arcs.clear();
00384 save.flow = flow;
00385 save.maxflow_iteration = maxflow_iteration;
00386 for(int i=0;i<2;++i){
00387 save.queue_first[i] = queue_first[i];
00388 save.queue_last[i] = queue_last[i];
00389 };
00390 save.TIME = TIME;
00391 save.started = true;
00392 };
00393 void stop_save(){
00394 save.started = false;
00395 };
00396
00397 void restore_arc(arc * dest, const arc & s){
00398 dest->r_cap = s.r_cap;
00399 };
00400
00401 void restore_node(node * dest, const node & s){
00402 dest->next = s.next;
00403 dest->parent = s.parent;
00404 dest->tr_cap = s.tr_cap;
00405
00406 dest->DIST = s.DIST;
00407
00408 dest->is_sink = s.is_sink;
00409 dest->TS = s.TS;
00410 };
00411
00412 void restore_saved(){
00413 for(int i=0;i<save.nodes.size();++i){
00414 restore_node(save.nodes[i].dest,save.nodes[i].saved);
00415 };
00416 for(int i=0;i<save.arcs.size();++i){
00417 restore_arc(save.arcs[i].dest,save.arcs[i].saved);
00418 };
00419 flow = save.flow;
00420 maxflow_iteration = save.maxflow_iteration;
00421 for(int i=0;i<2;++i){
00422 queue_first[i] = save.queue_first[i];
00423 queue_last[i] = save.queue_last[i];
00424 };
00425 TIME = save.TIME;
00426 };
00427
00428 void save_node(node * x){
00429 save.nodes.push_back(graph_save::node_saved(x));
00430 };
00431
00432 void save_arc(arc * x){
00433 save.arcs.push_back(graph_save::arc_saved(x));
00434 };
00435
00436 void save(node * x){
00437 if(save.started && !x->is_saved){
00438 save_node(x);
00439 x->is_saved = true;
00440 };
00441 };
00442
00443 void save(node & x){
00444 save(&x);
00445 };
00446
00447 void save(arc * x){
00448 if(save.started && !x->is_saved){
00449 save_arc(x);
00450 x->is_saved = true;
00451 };
00452 };
00453
00454 void save(arc & x){
00455 save(&x);
00456 };
00457 };
00458
00459
00460
00461
00462
00463
00464
00465
00466
00467
00468
00472
00473
00474
00475 template <typename captype, typename tcaptype, typename flowtype>
00476 inline typename Graph<captype,tcaptype,flowtype>::node_id Graph<captype,tcaptype,flowtype>::add_node(int num)
00477 {
00478 assert(num > 0);
00479
00480 if (node_last + num > node_max) reallocate_nodes(num);
00481
00482 if (num == 1)
00483 {
00484 node_last -> first = NULL;
00485 node_last -> tr_cap = 0;
00486 node_last -> is_marked = 0;
00487 node_last -> is_in_changed_list = 0;
00488
00489 node_last ++;
00490 return node_num++;
00491 }
00492 else
00493 {
00494 memset(node_last, 0, num*sizeof(node));
00495
00496 node_id i = node_num;
00497 node_num += num;
00498 node_last += num;
00499 return i;
00500 }
00501 }
00502
00503 template <typename captype, typename tcaptype, typename flowtype>
00504 inline void Graph<captype,tcaptype,flowtype>::add_tweights(node_id i, tcaptype cap_source, tcaptype cap_sink)
00505 {
00506 assert(i >= 0 && i < node_num);
00507
00508 tcaptype delta = nodes[i].tr_cap;
00509 if (delta > 0) cap_source += delta;
00510 else cap_sink -= delta;
00511 flow += (cap_source < cap_sink) ? cap_source : cap_sink;
00512 save(nodes[i]);
00513 nodes[i].tr_cap = cap_source - cap_sink;
00514 }
00515
00516 template <typename captype, typename tcaptype, typename flowtype>
00517 inline void Graph<captype,tcaptype,flowtype>::add_edge(node_id _i, node_id _j, captype cap, captype rev_cap)
00518 {
00519 assert(_i >= 0 && _i < node_num);
00520 assert(_j >= 0 && _j < node_num);
00521 assert(_i != _j);
00522 assert(cap >= 0);
00523 assert(rev_cap >= 0);
00524
00525 if (arc_last == arc_max) reallocate_arcs();
00526
00527 arc *a = arc_last ++;
00528 arc *a_rev = arc_last ++;
00529
00530 node* i = nodes + _i;
00531 node* j = nodes + _j;
00532
00533 a -> sister = a_rev;
00534 a_rev -> sister = a;
00535 a -> next = i -> first;
00536 i -> first = a;
00537 a_rev -> next = j -> first;
00538 j -> first = a_rev;
00539 a -> head = j;
00540 a_rev -> head = i;
00541 a -> r_cap = cap;
00542 a_rev -> r_cap = rev_cap;
00543 }
00544
00545 template <typename captype, typename tcaptype, typename flowtype>
00546 inline typename Graph<captype,tcaptype,flowtype>::arc* Graph<captype,tcaptype,flowtype>::get_first_arc()
00547 {
00548 return arcs;
00549 }
00550
00551 template <typename captype, typename tcaptype, typename flowtype>
00552 inline typename Graph<captype,tcaptype,flowtype>::arc* Graph<captype,tcaptype,flowtype>::get_next_arc(arc* a)
00553 {
00554 return a + 1;
00555 }
00556
00557 template <typename captype, typename tcaptype, typename flowtype>
00558 inline void Graph<captype,tcaptype,flowtype>::get_arc_ends(arc* a, node_id& i, node_id& j)
00559 {
00560 assert(a >= arcs && a < arc_last);
00561 i = (node_id) (a->sister->head - nodes);
00562 j = (node_id) (a->head - nodes);
00563 }
00564
00565 template <typename captype, typename tcaptype, typename flowtype>
00566 inline tcaptype Graph<captype,tcaptype,flowtype>::get_trcap(node_id i)
00567 {
00568 assert(i>=0 && i<node_num);
00569 return nodes[i].tr_cap;
00570 }
00571
00572 template <typename captype, typename tcaptype, typename flowtype>
00573 inline captype Graph<captype,tcaptype,flowtype>::get_rcap(arc* a)
00574 {
00575 assert(a >= arcs && a < arc_last);
00576 return a->r_cap;
00577 }
00578
00579 template <typename captype, typename tcaptype, typename flowtype>
00580 inline void Graph<captype,tcaptype,flowtype>::set_trcap(node_id i, tcaptype trcap)
00581 {
00582 assert(i>=0 && i<node_num);
00583 save(nodes[i]);
00584 nodes[i].tr_cap = trcap;
00585 }
00586
00587 template <typename captype, typename tcaptype, typename flowtype>
00588 inline void Graph<captype,tcaptype,flowtype>::set_rcap(arc* a, captype rcap)
00589 {
00590 assert(a >= arcs && a < arc_last);
00591 a->r_cap = rcap;
00592 }
00593
00594
00595 template <typename captype, typename tcaptype, typename flowtype>
00596 inline typename Graph<captype,tcaptype,flowtype>::termtype Graph<captype,tcaptype,flowtype>::what_segment(node_id i, termtype default_segm)
00597 {
00598 if (nodes[i].parent)
00599 {
00600 return (nodes[i].is_sink) ? SINK : SOURCE;
00601 }
00602 else
00603 {
00604 return default_segm;
00605 }
00606 }
00607
00608 template <typename captype, typename tcaptype, typename flowtype>
00609 inline void Graph<captype,tcaptype,flowtype>::mark_node(node_id _i)
00610 {
00611 node* i = nodes + _i;
00612 if (!i->next)
00613 {
00614
00615 if (queue_last[1]) queue_last[1] -> next = i;
00616 else queue_first[1] = i;
00617 queue_last[1] = i;
00618 i -> next = i;
00619 }
00620 i->is_marked = 1;
00621 }
00622
00623
00624 #endif